Problème de la galerie d'art

En informatique, plus précisément en géométrie algorithmique, le problème de la galerie d'art est un problème de visibilité bien étudié inspiré d'un problème réel. Il se formule comme suit :

« Quel est le nombre de gardiens (ou caméras) nécessaires pour surveiller une galerie d'art, et où faut-il les placer ? »

Formellement, la galerie d'art est représentée par un polygone simple et chaque gardien par un point du polygone. Un ensemble $S$ de points est dit surveiller ou couvrir un polygone si, pour tout point $p$ du polygone, il existe un point $q\in S$ tel que le segment de droite entre $p$ et $q$ est entièrement contenu dans le polygone. On peut aussi interpréter les gardiens comme des caméras de surveillance et demander que l'ensemble de la galerie soit visible en balayage.

Le théorème de la galerie d'art

Le théorème de la galerie d'art, démontré par Václav Chvátal, donne un majorant du nombre minimal de gardiens. Il dit :

« Pour garder un polygone simple à $n$ sommets, $\lfloor n/3\rfloor$ gardiens suffisent, et cette borne peut être atteinte ».

Historique

La question sur le nombre de gardiens nécessaires a été posée à Chvátal par Victor Klee en 1973^[1]. Chvátal l'a prouvé peu de temps après^[2]. La démonstration de Chvátal a été simplifiée par Steve Fisk, au moyen d'un argument basé sur une coloration de graphe^[3]. Fisk était alors professeur de mathématiques au Bowdoin College^[4].

Le problème et le théorème de la galerie d'art est moins connu que les thèmes standard de la géométrie algorithmique comme l'enveloppe convexe, la triangulation d'un polygone ou le calcul du diagramme de Voronoï, mais il figure dans divers manuels et cours de géométrie algorithmique^[5]^,^[6]^,^[7]^,^[8]^,^[9]^,^[10]^,^[11].

La démonstration de Fisk

La preuve de Steve Fisk^[12] est courte et élégante : elle figure dans le livre Raisonnements divins^[13]. La preuve est pour l'essentiel comme suit. On commence par trianguler le polygone (sans ajouter de nouveaux sommets). On procède comme pour la triangulation : On utilise le fait que tout polygone simple à au moins quatre sommets possède au moins deux « oreilles ». Une oreille est un triangle avec deux arêtes appartenant à la frontière du polygone, et la troisième située à l'intérieur du polygone. L'algorithme consiste à trouver une telle oreille, à la retirer du polygone, ce qui donne un nouveau polygone plus petit, donc 3-coloriable par récurrence, et ce coloriage est facilement étendu en coloriant le sommet supplémentaire de l'oreille avec la couleur restante. Dans une coloration en 3 couleurs, chaque triangle doit comporter les 3 couleurs. Les sommets de l'une des couleurs forment un ensemble de gardiens valide puisque chaque triangle du polygone est gardé par son sommet de cette couleur. Comme les trois couleurs partitionnent les n sommets du polygone, la couleur avec le moins de sommets définit un ensemble de gardiens valides avec au plus $\lfloor n/3\rfloor$ gardiens.

Illustration de la preuve

Pour illustrer la preuve, on considère le polygone ci-dessous. La première étape consiste à trianguler le polygone (voir Figure 1). Ensuite, on applique un $3$ -coloriage correct (Figure 2) et on observe qu'il y a $4$ sommets rouges, $4$ bleus et $6$ verts. La couleur ayant le moins de sommets est le bleu ou le rouge, donc le polygone peut être couvert par $4$ gardes (Figure 3). Ceci est en accord avec le théorème de la galerie d'art, car le polygone a $14$ sommets, et $\left\lfloor {\frac {14}{3}}\right\rfloor =4$ .

Figure 1
Figure 2
Figure 3

Variantes

Problème de la forteresse. Pour 13 sommets, il faut 5 gardiens.

La majoration de Chvátal reste valable si la restriction des gardiens aux sommets est affaiblie à des gardiens à tout point qui n'est pas à l'extérieur du polygone.

Il existe d'autres généralisations ou spécialisations du théorème de la galerie d'art original^[14]. Par exemple, pour les polygones orthogonaux, c'est-à-dire des polygones dont les côtés se joignent à angle droit, il suffit de $\lfloor n/4\rfloor$ gardiens. Il existe au moins trois démonstrations différentes de ce résultat, aucune n'est simple, l'une par Kahn, Maria Klawe et Daniel Kleitman; une autre par Anna Lubiw; et encore une autre par Jörg-Rüdiger Sack et Godfried Toussaint (en)^[15].

Un problème similaire consiste à déterminer le nombre minimal de gardiens nécessaires pour couvrir l'extérieur d'un polygone (c'est le « problème de la forteresse »): $\lceil n/2\rceil$ sont suffisants et parfois aussi nécessaires. En d'autre termes, couvrir l'extérieur, qui est infini, est plus exigeant que de couvrir l'intérieur fini^[16].

Complexité algorithmique

Le problème de calcul

Des algorithmes efficaces existent pour trouver des ensembles de gardiens placés aux sommets du polygone et qui vérifient la majoration de Chvátal, donc d'au plus $\lfloor n/3\rfloor$ gardiens.

David Avis et Godfried Toussaint^[17] ont prouvé qu'un tel placement peut être calculé en temps $O(n\log n)$ dans le pire des cas, en utilisant une méthode de diviser pour régner. Kooshesh et Moret 1992 ont donné un algorithme en temps linéaire en utilisant l'algorithme de la preuve de Fisk et l'algorithme linéaire de triangulation de Bernard Chazelle.

Un algorithme de calcul a été proposé par Couto, de Rezende et de Souza 2011 pour les gardiens placés aux sommets. Les auteurs ont mené de nombreux tests avec diverses classes de polygones qui ont montré que des solutions optimales peuvent être trouvées en un temps relativement court même pour des polygones à plusieurs milliers de sommets^[18].

Le problème de décision

Considéré comme un problème de décision, le problème de la galerie d'art est le problème de déterminer, étant donné un polygone et un entier k, si ce polygone peut être gardé avec au plus k gardiens. Ce problème est $\exists \mathbb {R}$ -complet^[19], où $\exists \mathbb {R}$ est la classe de complexité qui correspond au fragment existentiel de la théorie des corps réels clos. Les variations usuelles (comme restreindre les positions des gardiens aux sommets ou aux arêtes du polygone) sont NP-difficiles^[20].

Approximation

En ce qui concerne un algorithme d'approximation pour le nombre minimum de gardiens, Eidenbenz, Stamm et Widmayer 2001 ont montré que le problème est APX-difficile ; ceci implique qu'il est peu probable qu'un rapport d'approximation meilleur qu'une constante fixée puisse être réalisé par un algorithme d'approximation en temps polynomial. Toutefois, on ne connaît pas d'algorithme avec un rapport d'approximation constant. En revanche, une approximation logarithmique du nombre minimum de gardien peut être obtenue en réduisant le problème au problème de couverture par ensembles^[21]. Il a été montré par Pavel Valtr^[22] que le système d'ensembles dérivé d'un problème de galerie d'art a une dimension de Vapnik-Tchervonenkis bornée, ce qui permet d'appliquer des algorithmes de couverture par ensembles basés sur des ε-réseaux (en) dont le rapport d'approximation est le logarithme du nombre optimal de gardiens plutôt que du nombre de sommets du polygone^[23]. Pour le cas de gardiens sans restriction sur leur position, le nombre potentiellement infini des positions rend le problème encore plus difficile^[24]. Si l'on force les gardiens à occuper des positions sur une grille fine, un algorithme d'approximation logarithmique plus compliqué peut être obtenu sous des hypothèses additionnelles peu contraignantes^[25].

Dimensions supérieures

Si le musée est représenté en dimension supérieure par un polyèdre, alors il peut ne pas suffire de positionner un gardien sur chaque sommet pour couvrir la totalité du musée. Même si les surfaces du polyèdre sont alors sous surveillance, il est possible que des points à l'intérieur du polyèdre ne puissent pas être visibles^[26].

Notes

↑ O'Rourke 1987, p. 1.
↑ Chvátal 1975.
↑ Fisk 1978.
↑ Leghorn, « Mathematics professor dies of leukemia at 63 » [archive du 14 janvier 2017], The Bowdoin Orient, 2010.
↑ de Berg et al. 2008.
↑ Castelli Aleardi et Oudot 2012.
↑ Boissonnat 2017.
↑ Goodman et O'Rourke 2004.
↑ Edelsbrunner 1987.
↑ Pach et Agarwal 1995.
↑ Mehlhorn et Naeher 1999.
↑ Fisk 1978.
↑ Raisonnements divins, chapitre 35 : « Comment surveiller un musée ».
↑ Shermer 1992.
↑ O'Rourke 1987, p. 37-80, Kahn, Klawe et Kleitman 1983, Lubiw 1985 et Sack et Toussaint 1988.
↑ O'Rourke 1987, p. 146-154.
↑ Avis et Toussaint 1981.
↑ . Les données et les solutions pour ces tests sont disponibles dans Couto, de Rezende et de Souza 2011.
↑ Abrahamsen, Adamaszek et Miltzow 2017.
↑ O'Rourke 1987, p. 239–242; Aggarwal 1984; Lee et Lin 1986.
↑ Kumar Ghosh 2010.
↑ Valtr 1998.
↑ Brönnimann et Goodrich 1995.
↑ Deshpande et al. 2007
↑ Bonnet et Miltzow 2017.
↑ O'Rourke 1987, p. 255.

Références

Livres

Joseph O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987 (ISBN 0-19-503965-3, lire en ligne).
Mark de Berg, Otfried Cheong, Marc van Kreveld et Mark Overmars, Computational geometry : algorithms and applications, Springer Verlag, 2008, 3^e éd., 386 p. (ISBN 978-3-540-65620-3 et 3-540-65620-0, présentation en ligne, lire en ligne), chap. 3 (« Polygon Triangulation »), p. 45-61.
Luca Castelli Aleardi et Steve Oudot, Introduction à la géométrie algorithmique et ses applications, École polytechnique de Paris, coll. « Cours INF562 », 2012, 123 p. (lire en ligne).
Jean-Daniel Boissonnat, Géométrie algorithmique : des données géométriques à la géométrie des données : Leçon inaugurale du cours, Paris, Librairie Arthème Fayard et Collège de France, 2017, 73 p. (ISBN 978-2-213-70765-5 et 978-2-213-70512-5, lire en ligne).
Jacob E. Goodman et Joseph O'Rourke (éditeurs), The Handbook of Discrete and Computational Geometry, CRC Press, 2004, 2^e éd. (ISBN 1-58488-301-4).
(en) Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, Berlin/Heidelberg/Paris etc., Springer-Verlag, coll. « EATCS Monographs on Theoretical Computer Science » (n^o 10), 1987, 423 p. (ISBN 3-540-13722-X, lire en ligne).
(en) János Pach et Pankaj K. Agarwal, Combinatorial Geometry, New York/Chichester/Brisbane etc., John Wiley & Sons, 1995, 354 p. (ISBN 0-471-58890-3).
(en) János Pach et Micha Sharir, Combinatorial Geometry and its Algorithmic Applications : The Alcala Lectures, Providence, R.I., American Mathematical Society, coll. « Mathematical Surveys and Monographs » (n^o 152), 2009, 235 p. (ISBN 978-0-8218-4691-9, lire en ligne).
(en) Kurt Mehlhorn et Stefan Naeher, LEDA, A Platform for Combinatorial and Geometric Computing, Cambridge, Cambridge University Press, 1999, 1018 p. (ISBN 0-521-56329-1, lire en ligne).

Articles

Mikkel Abrahamsen, Anna Adamaszek et Tillmann Miltzow, « The Art Gallery Problem is $\exists \mathbb {R}$ -complete », preprint (arxiv),‎ 2017 (arXiv 1704.06969).
Alok Aggarwal, The art gallery theorem : Its variations, applications, and algorithmic aspects (thèse Ph. D.), Johns Hopkins University, 1984.
David Avis et Godfried T. Toussaint, « An efficient algorithm for decomposing a polygon into star-shaped polygons », Pattern Recognition, vol. 13, n^o 6,‎ 1981, p. 395–398 (DOI 10.1016/0031-3203(81)90002-9, lire en ligne).
Édouard Bonnet et Tillmann Miltzow, « An Approximation Algorithm for the Art Gallery Problem », Symposium on Computational Geometry,‎ 2017, p. 20:1-20:15, article n^o 20 (arXiv 1607.05527, lire en ligne).
Hervé Brönnimann et Michael T. Goodrich, « Almost optimal set covers in finite VC-dimension », Discrete and Computational Geometry, vol. 14, n^o 1,‎ 1995, p. 463–479 (DOI 10.1007/BF02570718).
Václav Chvátal, « A combinatorial theorem in plane geometry », Journal of Combinatorial Theory, Series B, vol. 18,‎ 1975, p. 39–41 (DOI 10.1016/0095-8956(75)90061-1).
Marcelo C. Couto, Pedro J. de Rezende et Cid C. de Souza, « An exact algorithm for minimizing vertex guards on art galleries », International Transactions in Operational Research, vol. 18, n^o 4,‎ 2011, p. 425–448 (DOI 10.1111/j.1475-3995.2011.00804.x).
Marcelo C. Couto, Pedro J. de Rezende et Cid C. de Souza, Benchmark instances for the art gallery problem with vertex guards, 2011 (lire en ligne).
Ajay Deshpande, Taejung Kim, Erik Demaine et Sanjay E. Sarma, « A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems », dans Proc. Workshop Algorithms and Data Structures, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 4619), 2007 (ISBN 978-3-540-73948-7, DOI 10.1007/978-3-540-73951-7_15), p. 163–174.
Stephan Eidenbenz, Christoph Stamm et Peter Widmayer, « Inapproximability results for guarding polygons and terrains », Algorithmica, vol. 31, n^o 1,‎ 2001, p. 79–113 (DOI 10.1007/s00453-001-0040-8, lire en ligne [archive du 24 juin 2003]).
Steve Fisk, « A short proof of Chvátal's watchman theorem », Journal of Combinatorial Theory, Series B, vol. 24, n^o 3,‎ 1978, p. 374 (DOI 10.1016/0095-8956(78)90059-X).
Subir Kumar Ghosh, « Approximation algorithms for art gallery problems in polygons », Discrete Applied Mathematics, vol. 158, n^o 6,‎ 2010, p. 718-722.
J. Kahn, Maria M. Klawe et Daniel J. Kleitman, « Traditional galleries require fewer watchmen », SIAM J. Alg. Disc. Meth., vol. 4, n^o 2,‎ 1983, p. 194–206 (DOI 10.1137/0604020).
Ali A. Kooshesh et Bernard M. E. Moret, « Three-coloring the vertices of a triangulated simple polygon », Pattern Recognition, vol. 25, n^o 4,‎ 1992, p. 443 (DOI 10.1016/0031-3203(92)90093-X).
Der-Tsai Lee et A. K. Lin, « Computational complexity of art gallery problems », IEEE Transactions on Information Theory, vol. 32, n^o 2,‎ 1986, p. 276–282 (DOI 10.1109/TIT.1986.1057165).
Anna Lubiw, « Decomposing polygonal regions into convex quadrilaterals », dans Proc. 1st ACM Symposium on Computational Geometry, 1985 (ISBN 0-89791-163-6, DOI 10.1145/323233.323247), p. 97–106.

Jörg-Rüdiger Sack et Godfried Toussaint, « Guard placement in rectilinear polygons », dans Godfried Toussaint (éditeur), Computational Morphology, North-Holland, 1988, p. 153–176.
Thomas Shermer, « Recent Results in Art Galleries », Proceedings of the IEEE, vol. 80, n^o 9,‎ 1992, p. 1384–1399 (DOI 10.1109/5.163407, lire en ligne).
Pavel Valtr, « Guarding galleries where no point sees a small area », Israel J. Math., vol. 104, n^o 1,‎ 1998, p. 1–16 (DOI 10.1007/BF02897056).

Voir aussi

Articles connexes

[1] O'Rourke 1987, p. 1.

[2] Chvátal 1975.

[3] Fisk 1978.

[4] Leghorn, « Mathematics professor dies of leukemia at 63 » [archive du 14 janvier 2017], The Bowdoin Orient, 2010.

[CompGeo-5] Berg et al. 2008.

[6] Castelli Aleardi et Oudot 2012.

[7] Boissonnat 2017.

[8] Goodman et O'Rourke 2004.

[9] Edelsbrunner 1987.

[10] Pach et Agarwal 1995.

[11] Mehlhorn et Naeher 1999.

[Fisk1978-12] Fisk 1978.

[13] Raisonnements divins, chapitre 35 : « Comment surveiller un musée ».

[14] Shermer 1992.

[15] O'Rourke 1987, p. 37-80, Kahn, Klawe et Kleitman 1983, Lubiw 1985 et Sack et Toussaint 1988.

[16] O'Rourke 1987, p. 146-154.

[17] Avis et Toussaint 1981.

[18] . Les données et les solutions pour ces tests sont disponibles dans Couto, de Rezende et de Souza 2011.

[19] Abrahamsen, Adamaszek et Miltzow 2017.

[20] O'Rourke 1987, p. 239–242; Aggarwal 1984; Lee et Lin 1986.

[21] Kumar Ghosh 2010.

[22] Valtr 1998.

[23] Brönnimann et Goodrich 1995.

[24] Deshpande et al. 2007

[25] Bonnet et Miltzow 2017.

[26] O'Rourke 1987, p. 255.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]